// run: $exec < input
#include <iostream>
#include <string>
#include <set>

int const maxn = 100007;
int next[maxn];
std::string s, t;
int n, m;

void get_next()
{
	next[0] = -1;
	int i = 0, j = -1;
	while(t[i] != '\0') {
		if(j == -1 || t[i] == t[j]) {
			i ++;
			j ++;
			next[i] = j;
		} else
			j = next[j];
	}
}

void kmp()
{
	std::set<int> print;
	get_next();
	int i = 0, j = 0, ans = 0, len = t.size();
	int swap = 0;
	while (s[i]) {
		if (j == -1 || s[i] == t[j]) {
			i++;
			j++;
		} else if (s[i] == t[j + 1] && s[i + 1] == t[j]) {
			i += 2;
			j += 2;
			swap += 2;
		} else
			j = next[j] + swap;

		if (j == len) {
			j = next[j];
			print.insert(i - 1);
			ans++;
		}
	}
	for (int i = 0; i < (int)s.size(); i++)
		if (print.count(i)) std::cout << "1";
		else std::cout << "0";
	std::cout << "\n";
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	while (T--) {
		std::cin >> n >> m;
		std::cin >> s >> t;
		kmp();
	}
}

